package LeetCode热题HOT100;

public class p309最佳买卖股票时机含冷冻期 {
    public int maxProfit(int[] prices) {

        int[][] dp=new int[prices.length][2];
        //dp[i][0/1]表示第i天的最大利润，第i天：不持有股票为dp[i][0]，持有股票为dp[i][1]
        //第i天不持有股票为dp[i][0]：当天卖出股票dp[i][0]=dp[i-1][1]+prices[i]  昨天也没有股票dp[i][0]=dp[i-1][0]
        //第i天 持有股票为dp[i][1]：当天买入股票dp[i][1]=dp[i-2][0]-prices[i]  昨天也持有 股票dp[i][1]=dp[i-1][1]

        dp[0][0]=0;//第一天不持股，则利润为0
        dp[0][1]=-prices[0];//第一天持股，则利润为-prices[0]

        for (int i = 1; i <prices.length; i++) {
            dp[i][0]=Math.max((dp[i-1][1]+prices[i]),dp[i-1][0]);//第i天不持股
            dp[i][1]=Math.max((i-2>=0?dp[i-2][0]:dp[0][0])-prices[i],dp[i-1][1]);//第i天持股，注意第二天(对应i=1)买股，那么第一天就只能为dp[0][0]
        }

        return Math.max(dp[prices.length-1][0],dp[prices.length-1][1]);
    }
}
